{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Factorization"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: smallestFactorization"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最小因式分解"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个正整数 <code>a</code>，找出最小的正整数 <code>b</code> 使得 <code>b</code> 的所有数位相乘恰好等于 <code>a</code>。</p>\n",
    "\n",
    "<p>如果不存在这样的结果或者结果不是 32 位有符号整数，返回 0。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>样例 1</strong></p>\n",
    "\n",
    "<p>输入：</p>\n",
    "\n",
    "<pre>48 \n",
    "</pre>\n",
    "\n",
    "<p>输出：</p>\n",
    "\n",
    "<pre>68</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>样例 2</strong></p>\n",
    "\n",
    "<p>输入：</p>\n",
    "\n",
    "<pre>15\n",
    "</pre>\n",
    "\n",
    "<p>输出：</p>\n",
    "\n",
    "<pre>35</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-factorization](https://leetcode.cn/problems/minimum-factorization/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-factorization](https://leetcode.cn/problems/minimum-factorization/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['48', '15']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def smallestFactorization(self, a):\n",
    "    \"\"\"\n",
    "    :type a: int\n",
    "    :rtype: int\n",
    "    \"\"\"\n",
    "    if a == 1:\n",
    "      return 1\n",
    "\n",
    "    factors = [ 2, 3, 5, 7 ]\n",
    "    power = { f : 0 for f in factors }\n",
    "\n",
    "    for f in factors:\n",
    "      while a % f == 0:\n",
    "        power[ f ] += 1\n",
    "        a //= f\n",
    "    if a > 1:\n",
    "      return 0\n",
    "\n",
    "    digits = list()\n",
    "    digits.extend( 9 for i in range( power[ 3 ] // 2 ) )\n",
    "    power[ 3 ] %= 2\n",
    "    digits.extend( 8 for i in range( power[ 2 ] // 3 ) )\n",
    "    power[ 2 ] %= 3\n",
    "    digits.extend( 7 for i in range( power[ 7 ] ) )\n",
    "\n",
    "    if power[ 3 ] > 0 and power[ 2 ] > 0:\n",
    "      digits.append( 6 )\n",
    "      power[ 3 ] -= 1\n",
    "      power[ 2 ] -= 1\n",
    "\n",
    "    digits.extend( 5 for i in range( power[ 5 ] ) )\n",
    "\n",
    "    if power[ 3 ] > 0:\n",
    "      digits.append( 3 )\n",
    "    if power[ 2 ] > 0:\n",
    "      digits.append( 2 ** power[ 2 ] )\n",
    "\n",
    "    ans = int( ''.join(map( str, reversed( digits ) )) )\n",
    "    return ans if -(2**31) <= ans < 2**31 else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestFactorization(self, num: int) -> int:\n",
    "        #贪心地分解\n",
    "        if num==1: return num\n",
    "        res=\"\"\n",
    "        for x in range(9,1,-1):\n",
    "            if num==1: break\n",
    "            while num%x==0:\n",
    "                res=str(x)+res\n",
    "                num//=x\n",
    "        if not res or num>1: return 0\n",
    "        ans=int(res)\n",
    "        return ans if ans<=((1<<31)-1) else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestFactorization(self, num: int) -> int:\n",
    "      if num < 10:  return num\n",
    "      stack = []\n",
    "      while num > 1 and len(stack) < 11:\n",
    "        for i in range(9, 0, -1):\n",
    "          if i == 1:  return 0\n",
    "          if num % i == 0:\n",
    "            stack.append(str(i))\n",
    "            num //= i\n",
    "            break\n",
    "      if len(stack) == 1: return 0\n",
    "      num = int(\"\".join(stack[::-1]))\n",
    "      if num > 2 ** 31 - 1: return 0\n",
    "      else: return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestFactorization(self, num: int) -> int:\n",
    "        if num == 1:\n",
    "            return 1\n",
    "        p2, p3, p5, p7 = 0, 0, 0, 0\n",
    "        while num % 2 == 0:\n",
    "            p2 += 1\n",
    "            num //= 2\n",
    "        while num % 3 == 0:\n",
    "            p3 += 1\n",
    "            num //= 3\n",
    "        while num % 5 == 0:\n",
    "            p5 += 1\n",
    "            num //= 5\n",
    "        while num % 7 == 0:\n",
    "            p7 += 1\n",
    "            num //= 7\n",
    "        if num > 1:\n",
    "            return 0\n",
    "        ans = []\n",
    "        rest2 = p2 % 3\n",
    "        ans.extend([8] * (p2 // 3))\n",
    "        # if rest2:\n",
    "        #     ans.append(2 ** rest2)\n",
    "        rest3 = p3 % 2\n",
    "        ans.extend([9] * (p3 // 2))\n",
    "        # if rest3:\n",
    "        #     ans.append(3)\n",
    "        if rest2 + rest3:\n",
    "            if not rest2:\n",
    "                ans.append(3)\n",
    "            elif not rest3:\n",
    "                ans.append(2 ** rest2)\n",
    "            else:\n",
    "                if rest2 == 2:\n",
    "                    ans.append(6)\n",
    "                    ans.append(2)\n",
    "                else:\n",
    "                    ans.append(6)\n",
    "        ans.extend([5] * p5)\n",
    "        ans.extend([7] * p7)\n",
    "        ans.sort()\n",
    "        val = int(''.join(map(str, ans)))\n",
    "        return val if val <= 2 ** 31 - 1 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestFactorization(self, num: int) -> int:\n",
    "        if num<2:\n",
    "            return num\n",
    "        ans=''\n",
    "        for i in range(9,1,-1):\n",
    "            while num%i==0:\n",
    "                num//=i\n",
    "                ans=str(i)+ans\n",
    "        if num<=1 and int(ans)<=2**31-1:\n",
    "            return int(ans)\n",
    "        else:\n",
    "            return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution: \n",
    "    def smallestFactorization(self, num: int) -> int:\n",
    "        INF = 2 ** 31 - 1\n",
    "        if num == 1:\n",
    "            return 1\n",
    "        ans = 0\n",
    "        mul = 1\n",
    "        while num > 1:\n",
    "            flag = True\n",
    "            for i in range(min(9, num), 1, -1):\n",
    "                if num % i == 0:\n",
    "                    num = num // i\n",
    "                    ans += mul * i\n",
    "                    if ans > INF:\n",
    "                        return 0 \n",
    "                    mul *= 10\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag:\n",
    "                return 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestFactorization(self, a: int) -> int:\n",
    "        if a <= 9:\n",
    "            return a\n",
    "        res = 0\n",
    "        weight = 1\n",
    "        for x in range(9, 1, -1):   #贪心，从9开始 因为 9 = 33\n",
    "            while a % x == 0:\n",
    "                a //= x\n",
    "                res = x * weight + res  #后面来的数字小，小的往左方\n",
    "                weight *= 10             #新放位置的权重\n",
    "\n",
    "                if res > 2**31 - 1:     #如果超范围了\n",
    "                    return 0\n",
    "        if a != 1:                      #如果是质数，分解不了  比如 13\n",
    "            return 0\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MAX = (1 << 31) - 1\n",
    "class Solution:\n",
    "    def smallestFactorization(self, num: int) -> int:\n",
    "        if num == 1:\n",
    "            return 1\n",
    "        data = []\n",
    "        for i in range(9, 1, -1):\n",
    "            while num % i == 0:\n",
    "                data.append(i)\n",
    "                num //= i\n",
    "        # print(num)\n",
    "        # print(data)\n",
    "        if not data or len(data) > len(str(MAX)) or num != 1:\n",
    "            return 0\n",
    "        ans = 0\n",
    "        for i in reversed(data):\n",
    "            ans *= 10\n",
    "            ans += i\n",
    "        return 0 if ans > MAX else ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestFactorization(self, num: int) -> int:\n",
    "        if num == 1:\n",
    "            return 1\n",
    "        p2, p3, p5, p7 = 0, 0, 0, 0\n",
    "        while num % 2 == 0:\n",
    "            p2 += 1\n",
    "            num //= 2\n",
    "        while num % 3 == 0:\n",
    "            p3 += 1\n",
    "            num //= 3\n",
    "        while num % 5 == 0:\n",
    "            p5 += 1\n",
    "            num //= 5\n",
    "        while num % 7 == 0:\n",
    "            p7 += 1\n",
    "            num //= 7\n",
    "        if num > 1:\n",
    "            return 0\n",
    "        ans = []\n",
    "        rest2 = p2 % 3\n",
    "        ans.extend([8] * (p2 // 3))\n",
    "        # if rest2:\n",
    "        #     ans.append(2 ** rest2)\n",
    "        rest3 = p3 % 2\n",
    "        ans.extend([9] * (p3 // 2))\n",
    "        # if rest3:\n",
    "        #     ans.append(3)\n",
    "        if rest2 + rest3:\n",
    "            if not rest2:\n",
    "                ans.append(3)\n",
    "            elif not rest3:\n",
    "                ans.append(2 ** rest2)\n",
    "            else:\n",
    "                if rest2 == 2:\n",
    "                    ans.append(6)\n",
    "                    ans.append(2)\n",
    "                else:\n",
    "                    ans.append(6)\n",
    "        ans.extend([5] * p5)\n",
    "        ans.extend([7] * p7)\n",
    "        ans.sort()\n",
    "        val = int(''.join(map(str, ans)))\n",
    "        return val if val <= 2 ** 31 - 1 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestFactorization(self, num: int) -> int:\n",
    "        if num == 1:\n",
    "            return 1\n",
    "\n",
    "        count = {2: 0, 3: 0, 5: 0, 7: 0}\n",
    "        count = {2:0, 3:0, 5:0, 7:0}\n",
    "        while num > 1:\n",
    "            valid = False\n",
    "            for divider in count:\n",
    "                if num % divider == 0:\n",
    "                    num /= divider\n",
    "                    count[divider] += 1\n",
    "                    valid = True\n",
    "            \n",
    "            if not valid:\n",
    "                return 0\n",
    "\n",
    "        result = ''\n",
    "        while count[3] > 1:\n",
    "            result += '9'\n",
    "            count[3] -= 2\n",
    "\n",
    "        # Combining 2 * 2 * 2 to make 8\n",
    "        while count[2] > 2:\n",
    "            result += '8'\n",
    "            count[2] -= 3\n",
    "        \n",
    "        while count[3] > 0 and count[2] > 0:\n",
    "            result += '6'\n",
    "            count[3] -= 1\n",
    "            count[2] -= 1\n",
    "\n",
    "        # Combining 2 * 2 to make 4\n",
    "        while count[2] > 1:\n",
    "            result += '4'\n",
    "            count[2] -= 2\n",
    "\n",
    "        # Add remaining 2s, 3s, 5s, and 7s as they are\n",
    "        for factor in count:\n",
    "            result += str(factor) * count[factor]\n",
    "\n",
    "        # Sort the result to get the smallest number\n",
    "        value = int(''.join(sorted(result)))\n",
    "        if value > 2147483647:\n",
    "            value = 0\n",
    "\n",
    "        return value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestFactorization(self, num: int) -> int:\n",
    "        #贪心地分解\n",
    "        if num==1: return num\n",
    "        res=\"\"\n",
    "        for x in range(9,1,-1):\n",
    "            if num==1: break\n",
    "            while num%x==0:\n",
    "                res=str(x)+res\n",
    "                num//=x\n",
    "        if not res or num>1: return 0\n",
    "        ans=int(res)\n",
    "        return ans if ans<=((1<<31)-1) else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestFactorization(self, num: int) -> int:\n",
    "      #贪心算法，从9开始枚举\n",
    "      if num <= 9: return num\n",
    "      res = ''\n",
    "      for x in range(9, 1, -1): # 答案中不可能出现 1\n",
    "        while num % x == 0:\n",
    "          num = num / x\n",
    "          res = str(x) + res\n",
    "          if int(res) > 2 ** 31 - 1:\n",
    "            return 0\n",
    "      \n",
    "      if num != 1: return 0\n",
    "      return int(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestFactorization(self, num: int) -> int:\n",
    "      if num < 10:  return num\n",
    "      stack = []\n",
    "      while num > 1 and len(stack) < 11:\n",
    "        for i in range(9, 0, -1):\n",
    "          if i == 1:  return 0\n",
    "          if num % i == 0:\n",
    "            stack.append(str(i))\n",
    "            num //= i\n",
    "            break\n",
    "      if len(stack) == 1: return 0\n",
    "      num = int(\"\".join(stack[::-1]))\n",
    "      if num > 2 ** 31 - 1: return 0\n",
    "      else: return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestFactorization(self, num: int) -> int:\n",
    "        #贪心地分解\n",
    "        if num==1: return num\n",
    "        res=\"\"\n",
    "        for x in range(9,1,-1):\n",
    "            if num==1: break\n",
    "            while num%x==0:\n",
    "                res=str(x)+res\n",
    "                num//=x\n",
    "        if not res or num>1: return 0\n",
    "        ans=int(res)\n",
    "        return ans if ans<=((1<<31)-1) else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestFactorization(self, num: int) -> int:\n",
    "        if num < 10:\n",
    "            return num\n",
    "        \n",
    "        res = 0\n",
    "        temp = 1\n",
    "\n",
    "        for i in range(9, 1, -1):\n",
    "            while num % i == 0:\n",
    "                num = int(num / i)\n",
    "                res = temp * i + res\n",
    "                temp =  temp * 10\n",
    "\n",
    "        if num != 1 or res > 2 ** 31 - 1:\n",
    "            print(num, res)\n",
    "            res = 0\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestFactorization(self, num: int) -> int:\n",
    "      if num < 10:  return num\n",
    "      stack = []\n",
    "      while num > 1 and len(stack) < 11:\n",
    "        for i in range(9, 0, -1):\n",
    "          if i == 1:  return 0\n",
    "          if num % i == 0:\n",
    "            stack.append(str(i))\n",
    "            num //= i\n",
    "            break\n",
    "      if len(stack) == 1: return 0\n",
    "      num = int(\"\".join(stack[::-1]))\n",
    "      if num > 2 ** 31 - 1: return 0\n",
    "      else: return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestFactorization(self, num: int) -> int:\n",
    "        @cache\n",
    "        def dfs(n):\n",
    "            if n < 10:\n",
    "                return n\n",
    "            ans = 0\n",
    "            for i in range(9,1,-1):\n",
    "                if n % i == 0:\n",
    "                    if 0 < dfs(n // i) < 2**31:\n",
    "                        ans = dfs(n // i)*10 + i\n",
    "                    break\n",
    "            return ans if ans < 2**31 else 0\n",
    "        return dfs(num)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestFactorization(self, num: int) -> int:\n",
    "        if num < 2:\n",
    "            return num\n",
    "        ans = 0\n",
    "        nul = 1\n",
    "        for i in range(9, 1, -1):\n",
    "            while num % i == 0:\n",
    "                num //= i\n",
    "                ans = i * nul + ans\n",
    "                nul *= 10\n",
    "        return ans if ans <= 1 << 31 - 1 and num == 1 else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestFactorization(self, num: int) -> int:\n",
    "        if num == 1:\n",
    "            return 1\n",
    "        ans = []\n",
    "        for i in range(9, 1, -1):\n",
    "            while num % i == 0:\n",
    "                ans.append(i)\n",
    "                num //= i \n",
    "            if num == 1:\n",
    "                break \n",
    "        if num != 1:\n",
    "            return 0\n",
    "        ret = int(''.join(map(str, ans[::-1])))\n",
    "        if ret.bit_length() >= 32:\n",
    "            return 0\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestFactorization(self, num: int) -> int:\n",
    "        if num == 1:\n",
    "            return 1\n",
    "        result, x, p = 0, 9, 1\n",
    "        while num > 1 and x > 1:\n",
    "            while not num % x:\n",
    "                result = x * p + result\n",
    "                num //= x\n",
    "                p *= 10\n",
    "            x -= 1\n",
    "        return result if num == 1 and result.bit_length() < 32 else 0\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestFactorization(self, num: int) -> int:\n",
    "        if num == 1:\n",
    "            return 1\n",
    "\n",
    "        count = {2: 0, 3: 0, 5: 0, 7: 0}\n",
    "        count = {2:0, 3:0, 5:0, 7:0}\n",
    "        while num > 1:\n",
    "            valid = False\n",
    "            for divider in count:\n",
    "                if num % divider == 0:\n",
    "                    num /= divider\n",
    "                    count[divider] += 1\n",
    "                    valid = True\n",
    "            \n",
    "            if not valid:\n",
    "                return 0\n",
    "\n",
    "        result = ''\n",
    "        while count[3] > 1:\n",
    "            result += '9'\n",
    "            count[3] -= 2\n",
    "\n",
    "        # Combining 2 * 2 * 2 to make 8\n",
    "        while count[2] > 2:\n",
    "            result += '8'\n",
    "            count[2] -= 3\n",
    "        \n",
    "        while count[3] > 0 and count[2] > 0:\n",
    "            result += '6'\n",
    "            count[3] -= 1\n",
    "            count[2] -= 1\n",
    "\n",
    "        # Combining 2 * 2 to make 4\n",
    "        while count[2] > 1:\n",
    "            result += '4'\n",
    "            count[2] -= 2\n",
    "\n",
    "        # Add remaining 2s, 3s, 5s, and 7s as they are\n",
    "        for factor in count:\n",
    "            result += str(factor) * count[factor]\n",
    "\n",
    "        # Sort the result to get the smallest number\n",
    "        value = int(''.join(sorted(result)))\n",
    "        if value > 2147483647:\n",
    "            value = 0\n",
    "\n",
    "        return value"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
